package main

import "fmt"

type ExamRoom struct {
	seat  []int
	count int
	N     int
}

func Constructor(n int) ExamRoom {
	return ExamRoom{make([]int, 0), 0, n}

}

//有序集合120ms 47%,10.4MB 5%
func (e *ExamRoom) Seat() int {
	if e.count == 0 {
		e.seat = append(e.seat, 0)
		e.count++
		return 0
	} else if e.count == 1 {
		if e.N-1-e.seat[0] > e.seat[0] {
			e.seat = append(e.seat, e.N-1)
			e.count++
			return e.N - 1
		} else {
			e.seat = append([]int{0}, e.seat...)
			e.count++
			return 0
		}
	}
	tmpseat := 0
	maxdistance := e.seat[0]
	seatBefore := 0
	sLen := len(e.seat)
	for i := 0; i < sLen-1; i++ {
		if (e.seat[i]+e.seat[i+1])/2-e.seat[i] > maxdistance {
			maxdistance = (e.seat[i]+e.seat[i+1])/2 - e.seat[i]
			tmpseat = (e.seat[i] + e.seat[i+1]) / 2
			seatBefore = i
		}
	}
	if e.N-1-e.seat[sLen-1] > maxdistance {
		tmpseat = e.N - 1
		seatBefore = sLen - 1
	}

	if tmpseat == 0 {
		e.seat = append([]int{0}, e.seat...)
		e.count++
	} else {
		e.seat = append(e.seat[:seatBefore+1], append([]int{tmpseat}, e.seat[seatBefore+1:]...)...)
		e.count++
	}
	fmt.Println(e.seat)
	return tmpseat
}

func (e *ExamRoom) Leave(p int) {
	for i, v := range e.seat {
		if v == p {
			e.seat = append(e.seat[:i], e.seat[i+1:]...)
			e.count--
			return
		}
	}
}

//优先队列，队列里的元素有优先级，一般用堆实现

func main() {
	e := Constructor(10)
	e.Seat()
	e.Seat()
	e.Seat()
	e.Seat()
	e.Seat()
	e.Seat()
	e.Seat()
	e.Seat()
	e.Seat()
	e.Seat()
	e.Leave(0)
	e.Leave(4)
	e.Seat()
	fmt.Println("err")
	e.Seat()
	e.Leave(8)
	e.Leave(9)
	e.Seat()
}
